import java.util.ArrayList;
import java.util.List;

public class qusetion_77 {
}

class Solution_77 {
    //解法一：我的思想
//    void dfs(int n,int k,int err[],int arr[],int m,List<List<Integer>> l){
//        //err用来标记每一个数是否是选中的状态，即状态数组;arr是已经选中并按顺序存放了的数组
//        if(m==k){//找到了一种可能
//            List<Integer> lchild=new ArrayList<>();
//            for (int i = 0; i < m; i++) {
//                lchild.add(arr[i]);
//            }
//            l.add(lchild);
//            return;//退出当前的循环
//        }
//        for (int i = 1; i <= n; i++) {
//            if(m==0||(err[i]==0&&i>arr[m-1])){//表示未选中的状态
//                //i>arr[m-1]这一步很重要，这一步是区别于全排列的关键步骤，eg:这题要求的是只是要求选中而不进行排序，即求的是C而不是A
//                //因为参与排列的每一个数都是不同的，所以大小也不同，所以我就想到了…… 1,2,3的全排列是123,132,213,231,312,321
//                //但是加上前一个数得大于后一个数的话就设123是符合条件的，也就是所要求的的C
//                arr[m]=i;
//                err[i]=1;
//                dfs(n,k,err,arr,m+1,l);
//                err[i]=0;//重新恢复
//            }
//        }
//    }
//    public List<List<Integer>> combine(int n, int k) {
//        //先考虑特殊的n或者特殊的k的情况
//        if(n==0||k==0)
//            return new ArrayList<List<Integer>>();//返回一个空的集合
//        List<List<Integer>> l=new ArrayList<>();
//        int err[]=new int[n+1];//我设置的标记数组下标是从1开始的，初始默认值是0，表示未选中的状态
//        int arr[]=new int[n];
//        dfs(n,k,err,arr,0,l);
//        return l;
//    }
    //解法二：通过标记上一层选中的值的办法，让下一层从这个数开始循环就可以省去一些多余的步骤，提高效率,同时可以省去标记函数,
    // 把一个结果数组换成集合的方式,还可以省略去掉记录层数
    void dfs(int n,int k,List<Integer> l,List<List<Integer>> result,int m){
        if(l.size()==k){
            result.add(new ArrayList<>(l));
            return;
        }
        for (int i = m; i <=n; i++) {
            l.add(i);
            dfs(n,k,l,result,i+1);
            l.remove(l.size()-1);//移除最末尾的数字
        }
    }
    public List<List<Integer>> combine(int n, int k) {
        //先考虑特殊的n或者特殊的k的情况
        if(n==0||k==0)
            return new ArrayList<List<Integer>>();//返回一个空的集合
        List<List<Integer>> result=new ArrayList<>();
        dfs(n,k,new ArrayList<Integer>(),result,1);
        return result;
    }

}